#
# @lc app=leetcode.cn id=2 lang=python3
#
# [2] 两数相加
#

# @lc code=start
# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:

        # 循环
        # res = ListNode()
        # cur_node = res
        # steptonext = 0
        # while l1 != None or l2 != None:

        #     if (l1.val + l2.val + steptonext) < 10:
        #         cur_node.val = l1.val + l2.val + steptonext
        #         steptonext = 0
        #     else:
        #         cur_node.val = (l1.val + l2.val + steptonext) - 10
        #         steptonext = 1

        #     if l1.next != None and l2.next != None:
        #         next_node = ListNode()
        #         cur_node.next = next_node
        #         cur_node = next_node
        #         l1 = l1.next
        #         l2 = l2.next

        #     elif l1.next == None and l2.next == None:
        #         break

        #     elif l1.next != None:
        #         next_node = ListNode()
        #         cur_node.next = next_node
        #         cur_node = next_node
        #         l1 = l1.next
        #         l2.val = 0

        #     elif l2.next != None:
        #         next_node = ListNode()
        #         cur_node.next = next_node
        #         cur_node = next_node
        #         l2 = l2.next
        #         l1.val = 0

        # if steptonext == 1:
        #     next_node = ListNode()
        #     cur_node.next = next_node
        #     cur_node = next_node
        #     cur_node.val = steptonext
        #     cur_node.next = None

        # return res

        # 递归
        def dfs(l, r, i):
            if not l and not r and not i:
                return None
            s = (l.val if l else 0) + (r.val if r else 0) + i
            node = ListNode(s % 10)
            node.next = dfs(l.next if l else None, r.next if r else None, s // 10)
            return node

        return dfs(l1, l2, 0)


# @lc code=end
